package com.study.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution_994 {
    private static class Point {
        public int row;
        public int col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public int orangesRotting(int[][] grid) {
        int rotting = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<Point> queue = new ArrayDeque<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new Point(i, j));
                }
            }
        }
        rot(grid, rows, cols, queue);
        while (!queue.isEmpty()) {

            rot(grid, rows, cols, queue);
            rotting++;
            printRotting(grid, rows, cols);
        }
        for (int[] row : grid) {
            for (int item : row) {
                if (item == 1) {
                    return -1;
                }
            }
        }
        return rotting;
    }

    private void rot(int[][] grid, int rows, int cols, Queue<Point> queue) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Point p = queue.poll();
            if (p == null) {
                continue;
            }
            //上
            if (p.row - 1 >= 0 && grid[p.row - 1][p.col] == 1) {
                grid[p.row - 1][p.col] = 2;
                queue.add(new Point(p.row - 1, p.col));
            }
            //下
            if (p.row + 1 < rows && grid[p.row + 1][p.col] == 1) {
                grid[p.row + 1][p.col] = 2;
                queue.add(new Point(p.row + 1, p.col));
            }
            //左
            if (p.col - 1 >= 0 && grid[p.row][p.col - 1] == 1) {
                grid[p.row][p.col - 1] = 2;
                queue.add(new Point(p.row, p.col - 1));
            }
            //右
            if (p.col + 1 < cols && grid[p.row][p.col + 1] == 1) {
                grid[p.row][p.col + 1] = 2;
                queue.add(new Point(p.row, p.col + 1));
            }
        }
    }

    private void printRotting(int[][] grid, int rows, int cols) {
        System.out.println();
        for (int i = 0; i < rows; i++) {
            System.out.println();
            for (int j = 0; j < cols; j++) {
                System.out.print(grid[i][j] + " ");
            }
        }
    }

    public static void main(String[] args) {
        Solution_994 solution_994 = new Solution_994();
        int[][] gird = {
                {2,1,1},
                {1,1,0},
                {0,1,1},
        };
        int i = solution_994.orangesRotting(gird);
        System.out.println("i = " + i);
    }
}
